package com.tgy.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: tgy
 * @Date: 12/8/20 9:43 AM
 *
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
public class _106_从中序与后序遍历序列构造二叉树 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        if (inorder == null ||
            postorder == null ||
            postorder.length == 0 ||
            inorder.length == 0 ||
            inorder.length != postorder.length ){

            return null;
        }

        Map<Integer, Integer> locs = new HashMap<>();

        for (int i = 0; i < inorder.length; i++) {

            locs.put(inorder[i],i);
        }

        return general(inorder,0,inorder.length - 1, postorder,0,postorder.length - 1,locs);
    }

    private TreeNode general(int[]inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, Map<Integer,Integer> locs) {

        if (inStart > inEnd) {

            return null;
        }
        int element = postorder[postEnd];
        TreeNode rootNode = new TreeNode(element);

        if (inStart == inEnd) {

            return rootNode;
        }

        Integer loc = locs.get(element);
        rootNode.right = general(inorder,loc + 1,inEnd,postorder,postEnd - (inEnd - loc),postEnd - 1,locs);
        rootNode.left = general(inorder,inStart,loc - 1,postorder,postStart,postEnd - (inEnd - loc) - 1,locs);

        return rootNode;
    }

}
